package code.mySpecializedTraining;

import utils.ListNode;

/**
 * @author 26029
 * @date 2025/4/28
 * @description
 */
public class Linked {
    // 148. 排序链表
    public ListNode sortList(ListNode head) {
        // 链表的归并排序
        // 如果没有或只有一个元素，直接返回
        if (head == null || head.next == null)
            return head;
        // 找到当前链表的中间节点
        ListNode slow = head, fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode temp = slow.next;
        slow.next = null; // 分离为左右链表[head->...->slow] [temp->...->fast]
        ListNode left = sortList(head);
        ListNode right = sortList(temp);
        // 合并两个链表
        ListNode preHead = new ListNode();
        ListNode pos = preHead;
        while (left != null && right != null) {
            if (left.val < right.val) {
                pos.next = left;
                left = left.next;
            } else {
                pos.next = right;
                right = right.next;
            }
            pos = pos.next;
        }
        if (left != null)
            pos.next = left;
        else
            pos.next = right;
        return preHead.next;
    }
}
